package linkedList.递归;

import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 翻转M到N个节点链表II92.java
 * @Description TODO https://leetcode-cn.com/problems/reverse-linked-list-ii/
 * @createTime 2021年03月08日 13:57:00
 */
public class 翻转M到N个节点链表II92 {
    /**
     * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
     *
     */

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        翻转M到N个节点链表II92 ii92 = new 翻转M到N个节点链表II92();
        ListNode listNode = ii92.reverseBetween(listNode1, 2,4);
        System.out.println(listNode);
    }
    public ListNode reverseBetween(ListNode head, int left, int right) {
        /**
         * 如果起始位置为1说明就是前 right 个节点的翻转
         * {@link 翻转前N个节点的链表}
         */
        if (left==1){
            return reversePreNNode(head,right);
        }
        ListNode node = reverseBetween(head.next, left-1,right-1);
        head.next=node;
        return head;
    }

    ListNode temp=null;
    private ListNode reversePreNNode(ListNode head, int i) {
        if (i==1){
            temp=head.next;
            return head;
        }
        ListNode newHeadNode = reversePreNNode(head.next, i - 1);
        head.next.next=head;
        head.next=temp;
        return newHeadNode;
    }
}
